package difficulty;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class L212 {
    public List<String> findWords(char[][] board, String[] words) {
        //dfs+tribe 时间复杂度O(n^2)
        int row = board.length;
        int column = board[0].length;
        Tribe tribe = new Tribe();
        for (String word : words) {
            tribe.insert(word);
        }
        List<String> res = new ArrayList<>();

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                Set<Integer> visited = new HashSet<>();
                findDfs(board, tribe, res, visited, "", i, j);
            }
        }
        return res;
    }

    public void findDfs(char[][] board, Tribe tribe, List<String> res, Set<Integer> visited, String s,
                        int r, int c) {
        int column = board[0].length;
        if (visited.contains(r * column + c)) return;

        char x = board[r][c];
        Tribe t = tribe.tribes[x - 'a'];
        if (t == null) return;
        s += x;
        if (t.isEnd) {
            res.add(s);
            t.isEnd = false;
            tribe.remove(s);
        }
        int row = board.length;
        visited.add(r * column + c);
        if (r + 1 < row) {
            findDfs(board, t, res, visited, s, r + 1, c);
        }
        if (r - 1 > -1) {
            findDfs(board, t, res, visited, s, r - 1, c);
        }
        if (c + 1 < column) {
            findDfs(board, t, res, visited, s, r, c + 1);
        }
        if (c - 1 > -1) {
            findDfs(board, t, res, visited, s, r, c - 1);
        }
        visited.remove(r * column + c);
    }

    public class Tribe {
        Tribe[] tribes = new Tribe[26];
        boolean isEnd;
        Tribe pre;

        public Tribe() {

        }

        public void insert(String s) {
            Tribe t = this;
            for (int i = 0; i < s.length(); i++) {
                Tribe tribe = t.tribes[s.charAt(i) - 'a'];
                if (tribe == null) {
                    tribe = new Tribe();
                    t.tribes[s.charAt(i) - 'a'] = tribe;
                    tribe.pre = t;
                }
                t = tribe;
            }
            t.isEnd = true;
        }

        public void remove(String s) {
            Tribe t = this;
            for (int i = s.length()-1; i >-1; i--) {
                boolean isEmpty = true;
                for (Tribe tribe : t.tribes) {
                    if(tribe != null) isEmpty = false;
                }
                t = t.pre;
                if(isEmpty){
                    t.tribes[s.charAt(i)] = null;
                }
            }
        }
    }
}